package org.octave.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author 391154
 * @since 2021/1/13 16:33
 */
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }

    /**
     * 前序遍历
     * 递归版本
     */
    public static void preOrder(TreeNode root) {
        if (root == null)
            return;
        System.out.print(root.val + ",");
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 前序遍历非递归版
     * 通过栈来实现
     */
    public static void preOrderIter(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + ",");
            // 前序遍历先放推有节点入栈
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    /**
     * 中序遍历-递归
     */
    public static void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + ",");
        inOrder(root.right);
    }

    /**
     * 中序遍历-非递归
     * 栈实现
     */
    public static void inOrderIter(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (!stack.isEmpty()) {
                root = stack.pop();
                System.out.print(root.val + ",");
                root = root.right;
            }
        }
    }

    /**
     * 后序遍历-递归
     */
    public static void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + ",");
    }

    /**
     * 后序遍历-非递归版
     */
    public static void postOrderIter(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode temp;
        while (!stack.isEmpty()) {
            temp = stack.peek();
            if (temp.left != null && root != temp.left && root != temp.right) {
                stack.push(temp.left);
            } else if (temp.right != null && root != temp.right) {
                stack.push(temp.right);
            } else {
                System.out.print(stack.pop() + ",");
                root = temp;
            }
        }
    }

    /**
     * 深度优先遍历
     * 及前序遍历
     */
    public static void dfs(TreeNode root) {

    }

    /**
     * 广度优先遍历
     */
    public static void treeBFS(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(root);
        while (!queue.isEmpty()) {
            // 队列为空时弹出
            TreeNode node = queue.poll();
            System.out.print(node.val + ",");
            // 如果当前左子树节点不为空，则将左子树推到队列中
            if (node.left != null) {
                queue.add(node.left);
            }
            // 如果右子树不为空，同理加入队列
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }
}
